package cn.kent.simple;

import java.util.*;

/**
 * 225. 用队列实现栈
 * 使用两个队列实现一个后入先出（LIFO）的栈
 * void push(int x) 将元素 x 压入栈顶。
 * int pop() 移除并返回栈顶元素。
 * int top() 返回栈顶元素。
 * boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 *
 * 三种方法：
 * 1. 两个队列  O(n) O(n)
 * 2. 一个队列->使用LinkedList，链表结构，直接offer(poll) O(n) O(1)
 * 3. 一个双端队列
 */
public class MyStack {
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        System.out.println(stack.empty());
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.empty());
        System.out.println(stack.top());
        System.out.println(stack.pop());
        System.out.println(stack.top());
    }

    // 使用双队列实现
    // 一个队列模拟栈，另一个队列操作用
    private Queue<Integer> q1;
    private Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        // 入栈：先加到q2末尾，然后将q1循环加到q2末尾，将q2赋给q1 -> 实现了q1的栈顺序
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        // 此处清空有两种方法，temp临时，或者重新new一个队列赋给q2
        // Queue<Integer> temp = q1;
        q1 = q2;
        // q2 = temp;
        q2 = new LinkedList<>();
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }


    // /**
    //  * 双端队列实现方式
    //  */
    // Deque<Integer> stack;
    // public MyStack() {
    //     stack = new ArrayDeque<>();
    // }
    //
    // public void push(int x) {
    //     stack.addFirst(x);
    // }
    //
    // public int pop() {
    //     return stack.pollFirst();
    // }
    //
    // public int top() {
    //     return stack.peekFirst();
    // }
    //
    // public boolean empty() {
    //     return stack.isEmpty();
    // }
}
